#ifndef _HSYNCH_H_
#define _HSYNCH_H_

#if defined(sun) || defined(_sun)
#    include <schedctl.h>
#endif

#include "../framework/cpp_framework.h"
#include "ITest.h"
#include "config.h"
#include "Synch_props.h"

using namespace CCP;

#define HSYNCH_NCLUSTERS 2 

typedef union CLHLockNode {
	bool locked;
	char align[CACHE_LINE_SIZE];
} CLHLockNode;

typedef struct CLHLockStruct {
	volatile CLHLockNode CACHE_ALIGN *Tail ;
	volatile CLHLockNode CACHE_ALIGN *MyNode[N_THREADS] ;
	volatile CLHLockNode CACHE_ALIGN *MyPred[N_THREADS] ;
} CLHLockStruct;


inline static void clhLock(CLHLockStruct *l, int pid) {
	l->MyNode[pid]->locked = true;
	l->MyPred[pid] = (CLHLockNode *)SWAPPO((void* volatile*)&l->Tail, (void *)l->MyNode[pid]);
	while (l->MyPred[pid]->locked == true) {
#ifdef _HSYNCH_H_
		;
#elif N_THREADS > USE_CPUS
		sched_yield();
#else
		;
#endif
	}
}

inline static void clhUnlock(CLHLockStruct *l, int pid) {
	l->MyNode[pid]->locked = false;
	l->MyNode[pid]= l->MyPred[pid];
#ifdef sparc
	Memory::write_barrier();	
#endif
}

CLHLockStruct *clhLockInit(void) {
	CLHLockStruct *l;
	int j;

	l = (CLHLockStruct*)getAlignedMemory(CACHE_LINE_SIZE, sizeof(CLHLockStruct));
	l->Tail = (CLHLockNode*) getAlignedMemory(CACHE_LINE_SIZE, sizeof(CLHLockNode));
	l->Tail->locked = false;

	for (j = 0; j < N_THREADS; j++) {
		l->MyNode[j] = (CLHLockNode*)getAlignedMemory(CACHE_LINE_SIZE, sizeof(CLHLockNode));
		l->MyPred[j] = null;
	}

	return l;
}

typedef struct HalfHSynchLockNode {
	struct HSynchLockNode *next;
	ArgVal arg_ret;
	int32_t pid;
	int32_t locked;
	int32_t completed;
} HalfHSynchLockNode;

typedef struct HSynchLockNode {
	struct HSynchLockNode *next;
	ArgVal arg_ret;
	int32_t pid;
	int32_t locked;
	int32_t completed;
	int32_t align[PAD_CACHE(sizeof(HalfHSynchLockNode))];
} HSynchLockNode;

typedef union HSynchLockNodePtr {
	struct HSynchLockNode *ptr;
	char pad[CACHE_LINE_SIZE];
} HSynchLockNodePtr;

typedef struct HSynchThreadState {
	HSynchLockNode *next_node;
#if defined(__sun) || defined(sun)
	schedctl_t *schedule_control;    
#endif
} HSynchThreadState;

typedef struct HSynchStruct {
	CLHLockStruct CACHE_ALIGN *central_lock ;
	volatile HSynchLockNodePtr CACHE_ALIGN Tail[HSYNCH_NCLUSTERS] ;
#ifdef DEBUG
	volatile int CACHE_ALIGN rounds ;
	volatile int counter;
#endif
} HSynchStruct;


HSynchStruct CACHE_ALIGN h_enqueue_lock ;
HSynchStruct CACHE_ALIGN h_dequeue_lock ;


void HSynchStructInit(HSynchStruct *l) {
	int i;

	l->central_lock = clhLockInit();
	for (i = 0; i < HSYNCH_NCLUSTERS; i++) {
		l->Tail[i].ptr = (HSynchLockNode*)getAlignedMemory(CACHE_LINE_SIZE, sizeof(HSynchLockNode));
		l->Tail[i].ptr->next = null;
		l->Tail[i].ptr->locked = false;
		l->Tail[i].ptr->completed = false;
	}
#ifdef DEBUG
	l->rounds = l->counter =0;
#endif
	Memory::write_barrier(); 
}

inline static void HSynchThreadStateInit(HSynchThreadState *st_thread, int pid) {
	st_thread->next_node = (HSynchLockNode*)getAlignedMemory(CACHE_LINE_SIZE, sizeof(HSynchLockNode));
#ifdef sun
	st_thread->schedule_control = schedctl_init();
#endif
}


class HSynchQueue : public ITest {
private:

	//helper function -----------------------------
	inline_ RetVal applyOp(HSynchStruct *l, RetVal (*sfunc)(ArgVal, int,PoolStruct*), HSynchThreadState *st_thread, ArgVal arg, int pid,PoolStruct *pool_node) {
		volatile HSynchLockNode *p;
		volatile HSynchLockNode *cur;
		register HSynchLockNode *next_node, *tmp_next;
		register int counter=0;

		next_node = st_thread->next_node;
		next_node->next = null;
		next_node->locked = true;
		next_node->completed = false;

#if defined(__sun) || defined(sun)
		schedctl_start(st_thread->schedule_control);
#endif
		cur = (volatile HSynchLockNode *)SWAPPO((void* volatile*)(&l->Tail[pid % HSYNCH_NCLUSTERS].ptr), next_node);
		cur->arg_ret = arg;
		cur->next = (HSynchLockNode *)next_node;
#if defined(__sun) || defined(sun)
		schedctl_stop(st_thread->schedule_control);
#endif
		st_thread->next_node = (HSynchLockNode *)cur;

		while (cur->locked) {                   // spinning
#if N_THREADS > USE_CPUS
			sched_yield();
#elif defined(sparc)
			Memory::read_write_barrier(); 
			Memory::read_write_barrier(); 
			Memory::read_write_barrier(); 
			Memory::read_write_barrier(); 
			Memory::read_write_barrier(); 
			Memory::read_write_barrier(); 
#else
			;
#endif
		}
		p = cur;                                // I am not been helped
		if (cur->completed)                     // I have been helped
			return cur->arg_ret;
#if defined(__sun) || defined(sun)
		schedctl_start(st_thread->schedule_control);
#endif
		clhLock(l->central_lock, pid);
#ifdef DEBUG
		l->rounds++;
#endif
		while (p->next != null && counter < HSYNCH_HELP_BOUND) {
			ReadPrefetch(p->next);
			counter++;
#ifdef DEBUG
			l->counter++;
#endif
			tmp_next = p->next;
			p->arg_ret = sfunc(p->arg_ret, p->pid,pool_node);
			p->completed = true;
			p->locked = false;
			p = tmp_next;
		}
		p->locked = false;                      // Unlock the next one
		clhUnlock(l->central_lock, pid);
#if defined(__sun) || defined(sun)
		schedctl_stop(st_thread->schedule_control);
#endif

		return cur->arg_ret;
	}

	struct HsynchSlotInfo {
		HSynchThreadState  deq_st_thread;
		HSynchThreadState  enq_st_thread;
		PoolStruct pool_node;

		HsynchSlotInfo* volatile _next;	

		HsynchSlotInfo(int id=-1) {
			init_pool(&pool_node, sizeof(ListNode));
			HSynchThreadStateInit(&deq_st_thread, id);
			HSynchThreadStateInit(&enq_st_thread, id);
		}
	};

	CCP::ThreadLocal<HsynchSlotInfo*>	_tls_slot_hsynch_info;
	CCP::AtomicReference<HsynchSlotInfo>	_tail_hsynch_slot;

	//list helper function --------------------------
	HsynchSlotInfo* get_new_hsynch_slot(int id) {
		HsynchSlotInfo* my_slot= new HsynchSlotInfo(id);
		_tls_slot_hsynch_info.set(my_slot);

		HsynchSlotInfo* curr_tail;
		do {
			curr_tail = _tail_hsynch_slot.get();
			my_slot->_next = curr_tail;
		} while(false == _tail_hsynch_slot.compareAndSet(curr_tail, my_slot));

		return my_slot;
	}

	inline_ static RetVal enqueue(ArgVal arg, int pid,PoolStruct* pool_node) {
		ListNode *node = (ListNode*)alloc_obj(pool_node);

		node->next = null;
		node->val = arg;
		last->next = node;
		last = node;
		return -1;
	}

	inline_ static RetVal dequeue(ArgVal arg, int pid,PoolStruct* pool_node) {
		ListNode *node = (ListNode *)first;
		if (first->next != null){
			first = first->next;
			return node->val;
		} else {
			return 0;
		}
	}

public:
	const int HSYNCH_HELP_BOUND; 
	//public operations ---------------------------
	HSynchQueue():HSYNCH_HELP_BOUND(3* _NUM_THREADS) 
	{
		_tail_hsynch_slot.set(new HsynchSlotInfo());
		HSynchStructInit(&h_enqueue_lock);
		HSynchStructInit(&h_dequeue_lock);	
	}

	virtual ~HSynchQueue() { }

	//enq ......................................................
	boolean add(final int iThread, final int inValue) {

		HsynchSlotInfo* my_slot = _tls_slot_hsynch_info.get();
		if(null == my_slot)
			my_slot = get_new_hsynch_slot(iThread);

		applyOp(&h_enqueue_lock, enqueue, &my_slot->enq_st_thread, (ArgVal) inValue, iThread,&my_slot->pool_node);
		return true;	
	}

	//deq ......................................................
	int remove(final int iThread, final int inValue) {
		HsynchSlotInfo* my_slot = _tls_slot_hsynch_info.get();
		if(null == my_slot)
			my_slot = get_new_hsynch_slot(iThread);

		return applyOp(&h_dequeue_lock, dequeue, &my_slot->deq_st_thread, (ArgVal) 1, iThread,&my_slot->pool_node);
	}

	//peek .....................................................
	int contain(final int iThread, final int inValue) {
		return _NULL_VALUE;
	}

	//general .....................................................
	int size() {
		return 0;
	}

	void entry(final int iThread,bool flag = false) {
		HsynchSlotInfo* my_slot = _tls_slot_hsynch_info.get();
		if(null == my_slot)
			my_slot = get_new_hsynch_slot(iThread);
	}
	void exit(final int iThread,bool flag = false) {
	}
	final char* name() {
		return "HSynchQueue";
	}

};

#endif

